/***
 * 链表
 * 22.链表中倒数第k个节点
 * 06.从尾到头打印链表
 * 24.反转链表
 * 25.合并两个排序的链表
 * 35.复杂链表的复制       (个_个)
 * 36.二叉搜索树与双向链表
 * 52.两个链表的第一个交点
 * 18.删除链表的节点
 * **/

#include <iostream>
#include <unordered_map>
#include <vector>
using std::cout;
using std::endl;
using std::unordered_map;
using std::vector;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int val = 0, ListNode *next = nullptr)
        : val(val), next(next) {}
};
// 复杂链表节点，带random指针
struct Node {
    int val;
    Node *next;
    Node *random;
    Node(int val = 0, Node *next = nullptr, Node *random = nullptr)
        : val(val), next(next), random(random) {}
};
class Solution
{
    // 22.
    ListNode *getKthFromEnd(ListNode *head, int k)
    {
        ListNode *slow = head, *fast = head;
        for (int i = 0; i < k; ++i) {
            fast = fast->next;
        }
        while (fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
    // 06.
    vector<int> reversePrint(ListNode *head)
    {
        vector<int> res;
        while (head) {
            res.push_back(head->val);
            head = head->next;
        }
        int i = 0, j = res.size() - 1;
        while (i < j) {
            std::swap(res[i++], res[j--]);
        }
        return res;
    }
    // 24.
    ListNode *reverseList(ListNode *head)
    {
        // 递归
        if (!head || !head->next) {
            return head;
        }
        ListNode *newHead = reverseList(head->next);
        // 1->2<-3<-4<-5
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
    ListNode *reverseList2(ListNode *head)
    {
        // 迭代 三指针
        ListNode *pre = nullptr, *cur = head;
        while (cur) {
            ListNode *post = cur->next;
            cur->next = pre;
            pre = cur;
            cur = post;
        }
        return pre;
    }
    // 25.
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        // 归并
        ListNode dummy = ListNode();
        ListNode *cur = &dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 ? l1 : l2;
        return dummy.next;
    }
    // 35.
    // unordered_map<Node *, Node *> _cache;
    Node *copyRandomList(Node *head)
    {
        // 递归 借助哈希表
        if (!head) {
            return nullptr;
        }
        auto it = _cache.find(head);
        if (it == _cache.end()) {
            Node *newHead = new Node(head->val);
            _cache.insert(std::make_pair(head, newHead));
            newHead->next = copyRandomList(head->next);
            newHead->random = copyRandomList(head->random);
        }
        return _cache[head];
    }
    Node *copyRandomList2(Node *head)
    {
        if (!head) {
            return nullptr;
        }
        Node *cur = head;
        // deepcopy node
        while (cur) {
            Node *node = new Node(cur->val);
            node->next = cur->next;
            cur->next = node;
            cur = cur->next->next;
        }
        // copy random
        cur = head;
        while (cur) {
            if (cur->random) {
                cur->next->random = cur->random->next;
            }
            cur = cur->next->next;
        }
        // 拆分链表并复原原链表
        Node *newHead = head->next;
        cur = head;
        while (cur) {
            Node *node = cur->next; // node新链表节点
            cur->next = cur->next->next;
            if (node->next) {
                node->next = node->next->next;
            }
            cur = cur->next;
        }
        return newHead;
    }
    // 52.
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        ListNode *curA = headA, *curB = headB;
        while (curA != curB) {
            curA = curA ? curA->next : headB;
            curB = curB ? curB->next : headA;
        }
        return curA;
    }
    // 18.
    ListNode *deleteNode(ListNode *head, int val)
    {
        if (!head) {
            return nullptr;
        }
        if (head->val == val) {
            return head->next;
        }
        ListNode *cur = head->next, *pre = head;
        while (cur) {
            if (cur->val == val) {
                pre->next = cur->next;
            }
            pre = cur;
            cur = cur->next;
        }
        return head;
    }

private:
    unordered_map<Node *, Node *> _cache;
#if 0
public:
    Node *treeToDoublyList(Node *root)
    {
        if (!root) {
            return nullptr;
        }
        inorderTraversal(root);
        head->left = pre;
        pre->right = head;
        return head;
    }
private:
    Node *pre = nullptr, *head = nullptr;
    void inorderTraversal(Node *root)
    {
        if (!root) {
            return;
        }
        inorderTraversal(root->left);
        if (pre) {
            pre->right = root;
        } else {
            head = root;
        }
        root->left = pre;
        pre = root;
        inorderTraversal(root->right);
    }
#endif
};

Solution solve = Solution();

int main()
{
    return 0;
}